import core.stdc.string;
import std.container.array;

import std.string;
import std.stdio;
import std.algorithm : swap;
import core.memory;

struct SqQueue(T,bool autoExten = false, bool useGC = true)
{
	
	this(uint size)
	{
		assert(size > 3);
		_size = size;
		//_data = new T[_size];
		static if(useGC) {
			_data = new T[_size];
		} else {
			auto len = T.sizeof * _size;
			_data = cast(T[])CAllocator.allocate(T.sizeof * size);
			GC.addRange(_data.ptr,len);
	
		}
	}
	
	~this()
	{
		static if(!useGC){
			GC.removeRange(_data.ptr);
			CAllocator.Delete(_data.ptr);
		}
		_data = null;
	}
	
	void clear()
	{
		while(!empty) {
			deQueue();
		}
		_front = _rear = 0;
	}
	
	@property bool empty() const
	{
		if(_rear == _front) return true;  //队空条件
		else return false;
	}
	
	@property bool full() const
	{
		if((_rear + 1) % _size == _front) return true; //队满
		else return false;
	}
	
	@property T front ()
	{
		assert(!empty());
		return _data[_front];
	}

	@property uint length()
	{
		return (_rear - _front + _size) % _size;
	}

	@property uint maxLength()
	{
            static if(autoExten) {
                return uint.max;
            } else {
		return _size - 1;
            }
	}
	
	bool enQueue(T x)
	{
               
		if(full()){ //队满
                     static if(autoExten) {
                        exten();
                     } else {
                        return false;
                    }
		}
		_data[_rear] = x;
		_rear= (_rear+1) % _size; //队尾指针加 1 取模
		return true;
	}
	
	T deQueue()
	{
		assert(!empty());
		auto x = _data[_front];
		_data[_front] = T.init;
		_front= (_front+1) % _size;  //队头指针加 1 取模
		return x;
	}
	static if (autoExten) {
	protected:
		void exten(){
                        writeln("queue auto exten");
			auto size = _size > 128 ?  _size + ((_size/3) * 2) : _size * 2;
			static if(useGC) {
				auto  data = new T[size];
			} else {
				auto len = T.sizeof * size;
				auto  data = cast(T[])CAllocator.allocate(T.sizeof * size);
				GC.addRange(data.ptr,len);

			}
			uint i  = 0;
			while(!empty) {
				data[i] = deQueue();
				++ i;
			}
			_size = size;
			_front = 0;
			_rear = i;
			static if(!useGC){
				GC.removeRange(_data.ptr);
				CAllocator.Delete(_data.ptr);
			}
			_data = data;
			writeln("queue auto extened size :", _size,"   used size:",length);
		}

		
	}
private:
	uint _front = 0;
	uint _rear = 0;
	T[] _data = null;//CAllocator.newArray!(T)(_size);
	uint _size;
};


void main()
{

	auto myq = SqQueue!(int,true,false)(5);
	writeln("init is empty = ",myq.empty);
	foreach(i;0..13){
		writeln("enQueue i =  ",i ,"  en value = ",myq.enQueue(i));
	}
	writeln("end is empty = ",myq.empty);
	writeln("end is full = ",myq.full);
	writeln("size  = ",myq.length);
	int i = 0;
	while(!myq.empty){
                writeln("\n");
		writeln("\tstart while! i = ", i);
		writeln("\tfront is = ",myq.front());
		writeln("\tdeQueue is = ",myq.deQueue());
		
		++ i;
	}
	writeln("size  = ",myq.length);
	int x = 2;
	myq.enQueue(x);
	writeln("front is = ",myq.front());
	writeln("size  = ",myq.length);
	x = 3;
	myq.enQueue(x);
	writeln("size  = ",myq.length);
	writeln("front is = ",myq.front());
	writeln("deQueue is = ",myq.deQueue());
	writeln("size  = ",myq.length);
	writeln("front is = ",myq.front());
}

import core.stdc.stdlib;
import std.conv : emplace;
import std.algorithm : max,min;
import core.stdc.string : memcpy;

@nogc:


template stateSize(T)
{
	static if (is(T == class) || is(T == interface))
		enum stateSize = __traits(classInstanceSize, T);
	else static if (is(T == struct) || is(T == union))
		enum stateSize = Fields!T.length || isNested!T ? T.sizeof : 0;
	else static if (is(T == void))
		enum size_t stateSize = 0;
	else
		enum stateSize = T.sizeof;
};

struct CAllocator
{
	
	static @trusted void * alloc(size_t bytes)
	{
		if (!bytes) return null;
		return malloc(bytes);
	}

	static @trusted void[] allocate(size_t bytes)
	{
		import core.stdc.stdlib : malloc;
		if (!bytes) return null;
		auto p = malloc(bytes);
		return p ? p[0 .. bytes] : null;
	}

	static @system bool deallocate(void[] b)
	{
		free(b.ptr);
		return true;
	}

	static @system void Delete(void * b) 
	{
		free(b);
	}

	static @system void Delete(T)(T b) if (is(T == class))
	{
		free(cast(void *)b);
	}

	static @system bool reallocate(ref void[] b, size_t s) 
	{
		if (!s)
		{
			deallocate(b);
			b = null;
			return true;
		}
		auto p = cast(ubyte*) realloc(b.ptr, s);
		if (!p) return false;
		b = p[0 .. s];
		return true;
	}

	static @system auto New(T, A...)(auto ref A args) 
	{
		auto m = allocate(max(stateSize!T, 1));
		if (!m.ptr) return null;
		scope(failure) deallocate(m);
		static if (is(T == class)) return emplace!T(m, args);
		else return emplace(cast(T*) m.ptr, args);
	}
	
	static T[] newArray(T)(size_t length)
	{
		if (!length) return null;
		auto m = allocate(T.sizeof * length);
		if (!m.ptr) return null;
		return uninitializedFillDefault(cast(T[]) m);
	}

	static T[] newArray(T)(size_t length,auto ref T init)
	{
		if (!length) return null;
		auto m = allocate(T.sizeof * length);
		if (!m.ptr) return null;
		auto result = cast(T[]) m;
		import std.traits : hasElaborateCopyConstructor;
		static if (hasElaborateCopyConstructor!T)
		{
			scope(failure) deallocate(m);
			size_t i = 0;
			static if (hasElaborateDestructor!T)
			{
				scope (failure)
				{
					foreach (j; 0 .. i)
					{
						destroy(result[j]);
					}
				}
			}
			for (; i < length; ++i)
			{
				emplace!T(result.ptr + i, init);
			}
		}
		else
		{
			fillWithMemcpy(result, init);
		}
		return result;
	}

	static bool expandArray(T)( T[] array,size_t delta, auto ref T init)
	{
		if (!delta) return true;
		void[] buf = array;
		if (!alloc.reallocate(buf, buf.length + T.sizeof * delta)) return false;
		immutable oldLength = array.length;
		array = cast(T[]) buf;
		scope(failure) uninitializedFillDefault(array[oldLength .. $]);
		import std.algorithm : uninitializedFill;
		array[oldLength .. $].uninitializedFill(init);
		return true;
	}

	bool expandArray(T, Allocator)(auto ref Allocator alloc, ref T[] array,
		size_t delta)
	{
		if (!delta) return true;
		immutable oldLength = array.length;
		void[] buf = array;
		if (!alloc.reallocate(buf, buf.length + T.sizeof * delta)) return false;
		array = cast(T[]) buf;
		uninitializedFillDefault(array[oldLength .. $]);
		return true;
	}

	private static void fillWithMemcpy(T)(void[] array, auto ref T filler) nothrow
	{
		import core.stdc.string : memcpy;
		if (!array.length) return;
		memcpy(array.ptr, &filler, T.sizeof);
		// Fill the array from the initialized portion of itself exponentially.
		for (size_t offset = T.sizeof; offset < array.length; )
		{
			size_t extent = min(offset, array.length - offset);
			memcpy(array.ptr + offset, array.ptr, extent);
			offset += extent;
		}
	}

	static private T[] uninitializedFillDefault(T)(T[] array) nothrow
	{
		fillWithMemcpy(array, T.init);
		return array;
	}
};
